package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by tiang on 2018/9/3.
 */
public class WordBreak {
    /**
     * Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,
     * determine if s can be segmented into a space-separated sequence of one or more dictionary words.

     Note:

     The same word in the dictionary may be reused multiple times in the segmentation.
     You may assume the dictionary does not contain duplicate words.
     Example 1:

     Input: s = "leetcode", wordDict = ["leet", "code"]
     Output: true
     Explanation: Return true because "leetcode" can be segmented as "leet code".
     Example 2:

     Input: s = "applepenapple", wordDict = ["apple", "pen"]
     Output: true
     Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
     Note that you are allowed to reuse a dictionary word.
     Example 3:

     Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     Output: false

     * @param s 字符串
     * @param wordDict 单词表
     * @return 字符串是否能按照单词表分割
     */
    public boolean wordBreak(String s, List<String> wordDict) {
//        wordDict.sort(Comparator.naturalOrder());
        return wordBreak(s, 0, wordDict, new Boolean[s.length()]);
    }

    /**
     * 单词s从index位置开始是否能按照单词表中的单词进行分割
     * @param s 源字符串
     * @param index 起始下标
     * @param wordDict 单词表
     * @param temp 以前遍历过的结果
     * @return 是否能够分割
     */
    private boolean wordBreak(String s, int index, List<String> wordDict, Boolean[] temp){
        // 分割完成
        if(index == s.length())
            return true;
        // 以前有分割过
        if(temp[index]!=null)
            return temp[index];
        for(int i=0;i<wordDict.size();i++){
            // 如果当前单词的第一个字符与s的index位置字符相同
            if(wordDict.get(i).charAt(0) == s.charAt(index)){
                // 计算单词的结束位置
                int endIndex = index+wordDict.get(i).length();
                if(endIndex>s.length())
                    continue;
                // 判断endIndex-index长度的子串是否与当前单词相同
                if(s.substring(index, endIndex).equals(wordDict.get(i))){
                    // 如果相同继续匹配
                    if(wordBreak(s, endIndex, wordDict, temp))
                        return true;
                }
            }
        }
        temp[index] = false;
        return false;
    }

    /**
     * Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to
     * construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

     Note:

     The same word in the dictionary may be reused multiple times in the segmentation.
     You may assume the dictionary does not contain duplicate words.
     Example 1:

     Input:
     s = "catsanddog"
     wordDict = ["cat", "cats", "and", "sand", "dog"]
     Output:
     [
     "cats and dog",
     "cat sand dog"
     ]
     Example 2:

     Input:
     s = "pineapplepenapple"
     wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
     Output:
     [
     "pine apple pen apple",
     "pineapple pen apple",
     "pine applepen apple"
     ]
     Explanation: Note that you are allowed to reuse a dictionary word.
     Example 3:

     Input:
     s = "catsandog"
     wordDict = ["cats", "dog", "sand", "and", "cat"]
     Output:
     []
     * @param s 源字符串
     * @param wordDict 字典表
     * @return 返回切割后的单词列表
     */
    public List<String> wordBreakToToken(String s, List<String> wordDict) {
        return wordBreakToToken(s, 0, wordDict, new List[s.length()+1]);
    }

    /**
     * 将字符串s从index位置开始的子串，按照字典表切割成单词序列
     * @param s 源字符串
     * @param index 起始index
     * @param wordDict 字典表
     * @param temp 以前切割过的记录
     * @return 切割后的序列
     */
    private List<String> wordBreakToToken(String s, int index, List<String> wordDict, List<String>[] temp){
        if(index == s.length()) {
            List<String> list = new ArrayList<>();
            list.add("");
            temp[index] = list;
            return list;
        }
        if(temp[index] != null)
            return temp[index];
        List<String> list = new ArrayList<>();
        for(int i=0;i<wordDict.size();i++){
            int endIndex = wordDict.get(i).length()+index;
            if(endIndex>s.length())
                continue;
            if(s.substring(index, endIndex).equals(wordDict.get(i))){
                List<String> subList = wordBreakToToken(s, endIndex, wordDict, temp);
                for(String str: subList){
                    if(!str.equals(""))
                        list.add(wordDict.get(i)+" "+str);
                    else
                        list.add(wordDict.get(i));
                }
            }
        }
        temp[index] = list;
        return list;
    }
}
